#include <iostream>
#include <vector>
#include <cmath>
#include "euler/divisor.hpp"
#include "euler.h"

BEGIN_PROBLEM(359, solve_problem_359)
	PROBLEM_TITLE("Hilbert's New Hotel")
	PROBLEM_ANSWER("40632119")
	PROBLEM_DIFFICULTY(1)
	PROBLEM_FUN_LEVEL(1)
	PROBLEM_TIME_COMPLEXITY("d")
	PROBLEM_SPACE_COMPLEXITY("1")
END_PROBLEM()

static bool is_square(int n)
{
	int x = (int)sqrt((double)n);
	return x*x == n;
}

// Display a simulation of the first N persons.
static void display_simulation(int N)
{
	std::vector<std::vector<int>> plan;
	for (int n = 1; n <= N; n++)
	{
		auto it = std::find_if(plan.begin(), plan.end(), 
			[n](const std::vector<int> &v) -> bool { 
				return is_square(v.back() + n);
		});
		if (it != plan.end())
			it->push_back(n);
		else
		{
			plan.push_back(std::vector<int>());
			plan.back().push_back(n);
		}
	}

	std::for_each(plan.cbegin(), plan.cend(), [](const std::vector<int> &v) {
		std::for_each(v.cbegin(), v.cend(), [](int x) {
			std::cout.width(4);
			std::cout << x;
		});
		std::cout << std::endl;
	});
}

#if 0
static int P(int f, int r)
{
	if (f == 1)
		return r*(r+1)/2;
	
	int d = (f + r) % 2 == 0? 1 : -1;
	if (f <= 3)
		return P(1,r+1) + d;

	if (f % 2 == 0)
	{
		int k = (f - 2) / 2;
		return P(2, r+2*k) + d*k;
	}
	else
	{
		int k = (f - 3) / 2;
		return P(3, r+2*k) + d*k;
	}
}
#else

static long long P(long long f, long long r)
{
	const long long M = 100000000;
	if (f == 1)
	{
		if (r % 2 == 0)
			return (r / 2 % M) * ((r+1) % M) % M;
		else
		//return (r*(r+1)/2) % M;
			return ((r+1) / 2 % M) * (r % M) % M;
	}
	
	int d = (f + r) % 2 == 0? 1 : -1;
	if (f <= 3)
		return (P(1,r+1) + d + M) % M;

	if (f % 2 == 0)
	{
		long long k = (f - 2) / 2;
		return ((P(2, r+2*k) + d*k) % M + M) % M;
	}
	else
	{
		long long k = (f - 3) / 2;
		return ((P(3, r+2*k) + d*k) % M + M) % M;
	}
}
#endif

static void check_simulation(int L)
{
	for (int f = 1; f <= L; f++)
	{
		for (int r = 1; r <= L + 1 - f; r++)
		{
			std::cout.width(4);
			std::cout << P(f,r);
		}
		std::cout << std::endl;
	}
}

static void solve_problem_359()
{
#if 0
	display_simulation(78);
	check_simulation(12);
#endif

#if 0
	std::cout << "P(1,1) = " << P(1,1) << std::endl;
	std::cout << "P(1,2) = " << P(1,2) << std::endl;
	std::cout << "P(2,1) = " << P(2,1) << std::endl;
	std::cout << "P(10,20) = " << P(10,20) << std::endl;
	std::cout << "P(25,75) = " << P(25,75) << std::endl;
	std::cout << "P(99,100) = " << P(99,100) << std::endl;
#endif

#if 1
	// 2^27 * 3*12
	long long sum = 0;
	for (int a = 0, f1 = 1; a <= 27; a++, f1 *= 2)
	{
		for (int b = 0, f2 = 1; b <= 12; b++, f2 *= 3)
		{
			long long f = (long long)f1 * f2;
			long long r = 71328803586048LL / f;
			long long p = P(f,r);
			sum += p;
			sum %= 100000000;
			// std::cout << "P(" << f << ", " << r << ") = " << p << std::endl;
		}
	}
	std::cout << sum << std::endl;
#endif
}
